
/**
 * @Project : Clion_ProgrammingExercises
 * @File : 0850
 * @Author : WangRuoyu 
 * @Date : 2023/5/22 11:27
 */

#include "iostream"
#include "queue"

using namespace std;

typedef pair<int, int> pii;

const int N = 150010;
const int inf = 0x3f3f3f3f;
int h[N];
int e[N];
int ne[N];
int w[N];
int idx;

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int &i: h) {
        i = -1;
    }

    for (int i = 0; i < m; ++i) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        if (a != b) {
            add(a, b, c);
        }
    }

    int dis[n + 1];
    bool st[n + 1];

    for (int i = 0; i <= n; ++i) {
        dis[i] = inf;
        st[i] = false;
    }
    dis[1] = 0;

    priority_queue<pii, vector<pii>, greater<>> pq;

    pq.push({0, 1});

    while (!pq.empty()) {
        pii node = pq.top();
        pq.pop();
        int id = node.second;
        int d = node.first;

        if (st[id]) continue;
        st[id] = true;
        for (int i = h[id]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dis[j] > d + w[i]) {
                dis[j] = d + w[i];
                pq.push(pii{dis[j], j});
            }
        }
    }

    if (dis[n] > 1e9) {
        printf("-1");
    } else {
        printf("%d", dis[n]);
    }

    return 0;
}